package leetcode;

public class SuperPow {

	public static void main(String[] args) {
		int[] b = {2, 5, 6, 7, 9};
		int a = 78267;
		SuperPow object = new SuperPow();
		System.out.println(object.superPow(a, b));
	}
	
	//1337不是素数，我们不能使用费马小定理
	private final int MOD = 1337;
	
	//1337的两个因子分别是7 和191，这两个数都是素数，所以我们有 6 * 190 = 1140
	//中国剩余定理
	//https://discuss.leetcode.com/topic/50591/fermat-and-chinese-remainder
	private final int MOD_MINUS = 1140;
	
	//费马小定理, a ^ (n - 1) mod n = 1;
	//所以我们只需要对b取1336的模即可
    public int superPow(int a, int[] b) {
        if(b == null || b.length <= 0){
        	return 0;
        }
        int pow = 0;
        for(int i = 0; i < b.length; i++){
        	pow = (pow * 10 + b[i]) % MOD_MINUS;
        }
        System.out.println("after mod: " + pow);
        return power(a, pow, MOD);
    }
	
    //求x的n次方
    public double myPow(double x, int n) {
        if(n == 0){
            return 1;
        }
        //与快速幂取余一样，我们同样利用x ^ n = (x ^ 2) ^ (n / 2), n为偶数
        //x ^ n = (x ^ 2) ^ (n / 2) * x, n为奇数
        double res = 1;
        boolean negativePow = n < 0;
        n = Math.abs(n);
        //另一种理解方法：比如求10 ^ 75
        //75 = 1001011
        //10 ^ 75 = 10 ^ 64  * 10 ^ 8 * 10^2 * 10^1
        //可见就是对二进制中为1的对应的x进行累剩
        while(n != 0){
            if( (n & 1) == 1){
                res = res * x;
            }
            x *= x;
            n >>>= 1;
        }
        return negativePow ? 1 / res : res;
    }
    
    
	//快速幂取模
	public int power(long a, int b, int c){
	    int res = 1;
	    a %= c;
	    // 令 k = a ^ 2 mod c
	    // 如果为偶数k ^ (b /2) mod c
	    // 如果为奇数k ^ (b /2) * a mod c
	    while (b != 0){
	    	//如果b是奇数,需要补一个a
	        if ( (b & 1) == 1){
	            res = (int)((res * a) % c);
	        }
	        a = (a * a) % c;
	        b >>>= 1;
	    }
	    return res;
	}
	
	//原来快速幂取模还有一个很重要的应用
	//按照费马小定理：a ^ (n - 1)  mod n = 1
	//我们可以迅速判断a的n - 1次幂取余n的结果是否为1，如果不为，那么n肯定不是素数
	
//	Miller和Rabin在Fermat测试上，建立了Miller-Rabin质数测试算法。
//
//	与Fermat测试相比，增加了一个二次探测定理：
//
//	如果p是奇素数，则 x^2 ≡ 1(mod p)的解为 x ≡ 1 或 x ≡ p - 1(mod p)
	
	//按照wikipedia上的解释：对于小于2^ 64的数只用选取a=2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37做测试即可
	
}
